package datastruct

import "fmt"

type ACTree struct {
	root *AcNode
}

type AcNode struct {
	value        string
	children     [26]*AcNode
	isEndingChar bool
	len          int     //距离根节点长度
	fail         *AcNode //添加了一个类似于kmp算法的next指针
}

func (t *ACTree) Insert(s string) {
	if t.root == nil {
		t.root = &AcNode{
			value:        "/",
			children:     [26]*AcNode{},
			isEndingChar: false,
		}
	}
	p := t.root
	for i := 0; i < len(s); i++ {
		index := int(s[i] - 'a')
		if p.children[index] == nil {
			p.children[index] = &AcNode{
				value:        string(s[i]),
				children:     [26]*AcNode{},
				isEndingChar: false,
			}
		}
		p = p.children[index]
	}
	p.isEndingChar = true
	p.len = len(s)
}
//时间复杂度
func (t *ACTree) BuildFailuerPointer() {
	//根节点的fail是空
	t.root.fail = nil
	//queue保存已知fail的节点
	q := []*AcNode{}
	q = append(q, t.root)
	for len(q) != 0 {
		p := q[0]
		q = q[1:len(q)]
		//给p的子节点寻找fail
		for i := 0; i < 26; i++ {
			pc := p.children[i]
			if pc == nil {
				continue
			}
			if pc == t.root {
				pc.fail = t.root
			} else {
				//利用已知p的fail求子节点pc的fail，类似于next
				q := p.fail
				for q != nil {
					qc := q.children[[]byte(pc.value)[0]-'a']
					if qc != nil { //qc！=nil说明下个字符匹配上了，就不需要找次长匹配前缀了
						pc.fail = qc
						break
					}
					//后退找次长匹配前缀，类似于k=next[k]
					q = q.fail
				}
				//q==nil说明遍历到了root也没找到最长匹配前缀，那fail就是root
				if q == nil {
					pc.fail = t.root
				}
			}
			q = append(q, pc)
		}
	}
}

//s是主串，t中保存的是模式串,遍历一遍主串就能找到所有匹配的模式串
func (t *ACTree) Match(s string) {
	n := len(s)
	//记录模式串的脚标，类似于j
	p := t.root
	for i := 0; i < n; i++ {
		index := int(s[i] - 'a')
		//如果p是root说明没有匹配的了
		for p.children[index] == nil && p != t.root {
			//找找其他的模式串最长前缀
			p = p.fail
		}
		//匹配到了主串第i个字符，而p之前的字符也是全都匹配上了
		p = p.children[index]
		//说明没找到，返回root
		if p == nil {
			p = t.root
		}
		tmp := p
		for tmp != t.root {
			//必须是模式串的结尾，才算是匹配
			if tmp.isEndingChar {
				pos := i - tmp.len + 1
				fmt.Println("匹配起始下标：", pos, ";长度:", tmp.len)
			}
			tmp = tmp.fail
		}
	}
}